package offer;

import java.util.LinkedList;
import java.util.List;

public class offerII_0110 {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result=new LinkedList<>();
        List<Integer> path=new LinkedList<>();
        int n= graph.length;
        path.add(0);
        search(result,path,graph,n,0);
        return result;
    }
    public void search(List<List<Integer>> result,List<Integer> path,int[][] graph,int n,int index){
        if(index==n-1){
            result.add(new LinkedList<>(path));
            return;
        }
        for(int i=0;i<graph[index].length;++i){
            path.add(graph[index][i]);
            search(result, path, graph, n,graph[index][i]);
            path.remove(path.size()-1);
        }
    }
}
